package com.zhao.utils;

import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import com.zhao.po.LineDetail;
import com.zhao.po.LineInfo;

/**
 * 这里是计算出最短路径的算法的类： 这个类需要穿个参数来初始化才能算出最短路径，所以常规的做成工具类不可行
 * @author Administrator
 *
 */
public class MyWeightedGraph {

	//定义一些静态的常量
	public static String LENGTH = "length";
	public static String COST = "cost";
	public static String TIME = "time";
	
	
	private class Vertex implements Comparable<Vertex> {
		private String vertexLabel;// 顶点标识
		private List<Edge> adjEdges;// 顶点的所有邻接边(点)
		private int dist;// 顶点到源点的最短距离
		private Vertex preNode;// 前驱顶点

		public Vertex(String vertexLabel) {
			this.vertexLabel = vertexLabel;
			adjEdges = new LinkedList<Edge>();
			dist = Integer.MAX_VALUE;
			preNode = null;
		}

		@Override
		public int compareTo(Vertex v) {
			if (this.dist > v.dist)
				return 1;
			else if (this.dist < v.dist)
				return -1;
			return 0;
		}
	}

	private class Edge {
		private int weight;// 边的权值(带权图)
		private Vertex endVertex;

		public Edge(int weight, Vertex endVertex) {
			this.weight = weight;
			this.endVertex = endVertex;
		}
	}

	private Map<String, Vertex> weightedGraph;// 存储图(各个顶点)
	private Vertex startVertex;// 单源最短路径的起始顶点
	private Vertex endVertex;// 单源最短路径的起始顶点
	private StringBuilder sb = new StringBuilder();

 
	/**
	 * 这里构建图传入两个参数： 
	 * @param roadLines  构建图要传递的路劲信息
	 * @param weight  我们要比较的权重,这里先暂时设计为以路径为权重
	 */
	public MyWeightedGraph(List<LineInfo> roadLines,String weight) {
		// TODO Auto-generated constructor stub
		weightedGraph = new LinkedHashMap<String, MyWeightedGraph.Vertex>();
		buildGraph(roadLines,weight);// 解析字符串构造图
	}

	private void buildGraph(List<LineInfo> roadLines, String myweight) {
		String startNodeLabel, endNodeLabel;
		Vertex startNode, endNode;
		int weight;
        String method="getLine"+myweight;
		
		for (LineInfo roadLine : roadLines) {
			startNodeLabel = String.valueOf(roadLine.getLinestart());
			endNodeLabel = String.valueOf(roadLine.getLineend());
			weight = Integer.valueOf(ReflectUtil.execute(roadLine, method).toString());

			endNode = weightedGraph.get(endNodeLabel);
			if (endNode == null) {
				endNode = new Vertex(endNodeLabel);
				weightedGraph.put(endNodeLabel, endNode);
			}

			startNode = weightedGraph.get(startNodeLabel);
			if (startNode == null) {
				startNode = new Vertex(startNodeLabel);
				weightedGraph.put(startNodeLabel, startNode);
			}
			Edge e = new Edge(weight, endNode);
			// 对于无向图而言,起点和终点都要添加边
			// endNode.adjEdges.add(e);
			startNode.adjEdges.add(e);
		}

	}

	private void dijkstra() {
		BinaryHeap<Vertex> heap = new BinaryHeap<MyWeightedGraph.Vertex>();
		init(heap);// inital heap

		while (!heap.isEmpty()) {
			Vertex v = heap.deleteMin();
			List<Edge> adjEdges = v.adjEdges;// 获取v的所有邻接点
			for (Edge e : adjEdges) {
				Vertex adjNode = e.endVertex;
				// update
				if (adjNode.dist > e.weight + v.dist) {
					adjNode.dist = e.weight + v.dist;
					adjNode.preNode = v;
				}
			} // end for

			// 更新之后破坏了堆序性质,需要进行堆调整,这里直接重新构造堆(相当于decreaseKey)
			heap.buildHeap();
		}

	}

	private void init(BinaryHeap<Vertex> heap) {
		startVertex.dist = 0;// 源点到其自身的距离为0
		for (Vertex v : weightedGraph.values()) {
			heap.insert(v);
		}
	}

	public void showDistance() {
		for (Vertex v : weightedGraph.values()) {
			printPath(v);
			System.out.println();
			System.out.println("顶点 " + v.vertexLabel + "到源点" + startVertex.vertexLabel + " 的距离: " + v.dist);
		}
	}

	// 打印源点到 end 顶点的 最短路径
	private void printPath(Vertex end) {
		if (end.preNode != null)
			printPath(end.preNode);
		sb.append(end.vertexLabel + "-");
	}

	// ============下面是为了更加的适应我们项目需求而修改的方法
//	public StepResult getMinStep(int start, int end) {
//		StepResult step=new StepResult();
//		if (weightedGraph != null) {
//			// 设置起始点
//			startVertex = weightedGraph.get(String.valueOf(start));
//			endVertex = weightedGraph.get(String.valueOf(end));
//			
//			dijkstra();
//			printPath(endVertex);
//			System.out.println();
//		}
//        step.setMinstep(sb.toString().substring(0, sb.toString().length()-1));
//        step.setLength(endVertex.dist);
//		return step;
//	}

	/**
	 * 改进的获取最短路径的方法
	 * @param start
	 * @param end
	 * @return
	 */
	public  LineDetail getMinStep(int start, int end) {
		LineDetail step=new LineDetail();
		if (weightedGraph != null) {
			// 设置起始点
			startVertex = weightedGraph.get(String.valueOf(start));
			endVertex = weightedGraph.get(String.valueOf(end));
			
			dijkstra();
			printPath(endVertex);
		}
		step.setStartpoint(start);
		step.setEndpoint(end);
		step.setLinedetail(sb.toString().substring(0, sb.toString().length()-1));
		step.setLinestate(true);
		return step;
	}
}